package Year22_Month05.day23;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;

public class 前K个高频元素 {
    public int[] topKFrequent(int[] nums, int k) {
        //首先定义一个Map用来存储每个元素和其出现的顺序
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int key = nums[i];
            map.put(key, map.getOrDefault(key,0) + 1);
        }

        //然后把这些映射关系全部返回,用一个set接收起来
        Set<Map.Entry<Integer,Integer>> sets = map.entrySet();
        PriorityQueue<Map.Entry<Integer,Integer>> minQue = new PriorityQueue<>(
                //其实这一行是完全可以省略的，因为优先级队列本来就是默认小根堆
                (o1,o2) -> (o1.getValue() - o2.getValue())
        );
        //然后就是遍历所有的映射关系，根据值来进行堆排序。
        for(Map.Entry<Integer,Integer> set:sets){
            minQue.add(set);
            if(minQue.size() > k){
                minQue.poll();
            }
        }
        int[] arr = new int[k];
        //然后堆当中剩余的键值对一个一个往出删，删一个存一个的key
        for(int i = k - 1;i >= 0;i--){
            arr[i] = minQue.poll().getKey();
        }
        return arr;
    }
}
